<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>图类</title>
</head>
<body>
<script src="dict.js"></script>
<script src="queue.js"></script>
<script>
    function Graph() {
        // 属性
        this.vertexes = [] // 存储顶点
        this.adjList = new Dictionay() // 存储边

        // 添加方法
        Graph.prototype.addVertex = function (v) {
            this.vertexes.push(v)
            this.adjList.set(v, [])
        }

        Graph.prototype.addEdge = function (v, w) {
            this.adjList.get(v).push(w)
            this.adjList.get(w).push(v)
        }

        Graph.prototype.toString = function () {
            var resultStr = ""
            for (var i = 0; i < this.vertexes.length; i++) {
                resultStr += this.vertexes[i] + "->"
                var adj = this.adjList.get(this.vertexes[i])
                for (var j = 0; j < adj.length; j++) {
                    resultStr += adj[j] + " "
                }
                resultStr += "\n"
            }
            return resultStr
        }

        // 初始化颜色
        Graph.prototype.initializeColor = function () {
            var colors = []
            for (var i = 0; i < this.vertexes.length; i++) {
                colors[this.vertexes[i]] = "white"
            }
            return colors
        }

        // 广度优先算法
        Graph.prototype.bfs = function (v, handler) {
            // 1.初始化颜色
            var color = this.initializeColor()

            // 2.创建队列
            var queue = new Queue()

            // 3.将传入的顶点放入队列中
            queue.enqueue(v)

            // 4.从队列中依次取出和放入数据
            while (!queue.isEmpty()) {
                // 4.1.从队列中取出数据
                var qv = queue.dequeue()

                // 4.2.获取qv相邻的所有顶点
                var qAdj = this.adjList.get(qv)

                // 4.3.将qv的颜色设置成灰色
                color[qv] = "gray"

                // 4.4.将qAdj的所有顶点依次压入队列中
                for (var i = 0; i < qAdj.length; i++) {
                    var a = qAdj[i]
                    if (color[a] === "white") {
                        color[a] = "gray"
                        queue.enqueue(a)
                    }
                }

                // 4.5.因为qv已经探测完毕, 将qv设置成黑色
                color[qv] = "black"

                // 4.6.处理qv
                if (handler) {
                    handler(qv)
                }
            }
        }

        // 深度优先搜索
        Graph.prototype.dfs = function (handler) {
            // 1.初始化颜色
            var color = this.initializeColor()

            // 2.遍历所有的顶点, 开始访问
            for (var i = 0; i < this.vertexes.length; i++) {
                if (color[this.vertexes[i]] === "white") {
                    this.dfsVisit(this.vertexes[i], color, handler)
                }
            }
        }

        // dfs的递归调用方法
        Graph.prototype.dfsVisit = function (u, color, handler) {
            // 1.将u的颜色设置为灰色
            color[u] = "gray"

            // 2.处理u顶点
            if (handler) {
                handler(u)
            }

            // 3.u的所有邻接顶点的访问
            var uAdj = this.adjList.get(u)
            for (var i = 0; i < uAdj.length; i++) {
                var w = uAdj[i]
                if (color[w] === "white") {
                    this.dfsVisit(w, color, handler)
                }
            }

            // 4.将u设置为黑色
            color[u] = "black"
        }
    }

    // 测试代码
    var graph = new Graph()

    // 添加顶点
    var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
    for (var i = 0; i < myVertexes.length; i++) {
        graph.addVertex(myVertexes[i])
    }

    // 添加边
    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('A', 'D');
    graph.addEdge('C', 'D');
    graph.addEdge('C', 'G');
    graph.addEdge('D', 'G');
    graph.addEdge('D', 'H');
    graph.addEdge('B', 'E');
    graph.addEdge('B', 'F');
    graph.addEdge('E', 'I');

    // 打印结果
    alert(graph)

    // 调用广度优先算法
    var result = ""
    graph.bfs(graph.vertexes[0], function (v) {
        result += v + " "
    })
    alert(result) // A B C D E F G H I

    // 调用深度优先算法
    result = ""
    graph.dfs(function (v) {
        result += v + " "
    })
    alert(result) // A B E I F C D G H
</script>
</body>
</html>